***Subsecv. de sum. maxima***
1) - se fac sume partiale sum[i]=sum[i-1]+A[i];
- initializare: min=0;
-recurenta:   Bst[i]= sum[i]-min; 
		      min=(min>sum[i])?sum[i] : min;
- s.d.s.m se va retine in variabila bstsum (complex O(N) )

2) Divide et impera
-impartim sirul in 2 jumatati (st,mid);(mid+1,dr) si apoi calculam s.d.s.m din cele 2 intervale cat si o subsecventa comuna (cu ajutorul sufixelor si prefixelor)
-procedeul se repeta si rezultatu final e maxiumul valorilor de mai sus (complex. O(N log N) )
- rezultatul este maximul dintre Sufix+Prefix si rezultatul din intervalele (l, mij) , (mij + 1, r)

int getMax(int st, int dr) 
{
    if (st == dr)
		return a[l];
    int mij = (st + dr) / 2;
    int bestL = getMax(l, mij);
    int bestR = getMax(mij + 1, r);
    suf = 0; 
    pre = 0; 
    maxSuf = -OO; 
    maxPre = -OO;
    for (i = mij; i >= l; i--) 
    {
        suf += a[i];
        if (maxSuf < suf) 
			maxSuf = suf;
    }
    for (i = mij + 1; i <= r; i++) 
    {
        pre += a[i];
        if (maxPre < pre) 
			maxPre = pre;    
    }
    return max(bestL, max(bestR, maxPre + maxSuf)); 

}


3) P.D clasica - recuranta: best[i]=max(a[i],best[i-1]+a[i]) - O(N)

4) P.D. - o alta abordare a PD este partitionarea sirului in subsecvente de suma negativa
-in practica se foloseste recuranta: sum+=a[i]; sum=(sum<0)?0:sum; bestSum=(sum>bestSum)?sum:bestSum; => O(N) (neoptim fata de 3) )

*** S.d.s.m 2D ***
1) Semisume - O(N^4)

2)PD - tre' sa reduceam probl. la una 1D , deci facem semisumele pe coloane pe directia sus-jos si apoi pentru 2 linii fixate i1,i2 determinam in O(N) s.d.s.m 
- complexitate totala ~ O(N^3)

*** S.d.s.m Querys ***
- determinarea s.d.s.m in Q intervale

1) O(N*Q) - ideea initiala e cea "bruta" , adica raspundem la fiecare query in O(N) la toate cele Q intrebari

2) PD - O(N+M*sqrt(N)) - Notam: sqrt(N)=K
-impartim sirul in K parti afland 3 valori care ne vor ajuta  : - max[i] - cea mai mare valoare sum[j] din interval
																- min[i] - cea mai mica valoare sum[j] din interval
																- bst[i] - valoarea s.d.s.m. din secventa noastra
- ne folosim de algoritmii cu sifix+prefix si valorile calulate anterior pentru orice [x..y] cu x si y in subsecvente K diferite

3) Arbori de intervale - O(N+M*log(N))
- facem sume paritale ( sum ) si apoi aflam max[] , min[] pe fiecare interval
- min va fi minimul din vect sum , iau max maximul

*** Secventa de modul minim *** (modului || sumei elementelor) - O(N*log N)
- facem sume partiale si tre' sa gasim [i..j] a.i. |sum[i]-sum[j]| minim , deci pentru i<j => | sum[i]-sum[j] | = sum[j]-sum[i]
- soram elementele vect. sum si indicii acestora 
- soltia se va gasi intre 2 elemente consecutive din vectorul sortat , unde |sum[i]-sum[i+1]| minim 
- determinarea secventei se face liniar insa complexitatea minima este data de sortare ( heap / quick )

*** S.d.s.m. de lungime minim F ***
-dinamica: bst[i]=max(a[i],bst[i-1]+a[i]);
-facem sum. part. : sum[i]=a[i]+sum[i-1];
-rezultat: rez[i]=sum[i]-sum[i-F+1]+bst[i-F+1] deoarece 
( a[i]+a[i-1]+...+a[i-F+2] ) + bst[i-F+1] =( sum[i]-sum[i-F+1] ) + bst[i-F+1];
________________________       __________	
		 F-1 el.	1 el.
		_______________________
			F el.
					
*** Aflarea unei secv. de lungime minim K cu minimul el. maxim ***
1) Heap-uri - consturuim un min-heap din care scoatem si bagam cate un element in O(log K)
-complexitate: O(N*log K)

2) RMQ

3) Deque - observatia initiala este ca solutia optima contine exact  K elemente deci folosim un deque
 si memoram solutia cand nr de elemente e K 
- ca sa optimizam stim ca este inutil sa tinem in deque elementele mai mari decat ultimul element introdus 
- dupa ce am format initial deque-ul cu proprietatile de mai sus cand i>=K puteam construi solutia 
- elementele intruduse acum K+1 pasi trebuie scoase din deque
- deque-ul va retine maxim K perechi (A,B) , unde A=sir[i] si B=i		
-complexitate totala : O(N)

*** Aflarea unei secv. de lungime minim K cu minimul el. maxim - 2D ***	
-pentru 2 linii fixate i1,i2 folosm un algoritm asemanator cu cel de mai sus 1D 
   * Deque - O(N^3)
   * Heap -  O(N^3 log K)
   
Generalizare: Pentru a trece de la o problema 2D la o problema 1D se fixeaza 2 valori pentru linie sau coloana si se imparte problema in N^2 subprobleme 1D